package algocasts;

public class P121_NumOfDigitOne {
    // Time: O(n * log_10(n)), Space: O(1)
    public int countDigitOne_BruteForce(int n) {
        if (n < 1) return 0;
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int num = i;
            while (num != 0) {
                if (num % 10 == 1) ++count;
                num /= 10;
            }
        }
        return count;
    }

    // Time: O(log_10(n))  Space: O(1)
    public int countDigitOne_Math(int n) {
        if (n < 1) return 0;
        long count = 0, factor = 1;
        while (n / factor != 0) {
            long digit = (n / factor) % 10;
            long high = n / (10 * factor);
            if (digit == 0) {
                count += high * factor;
            } else if (digit == 1) {
                count += high * factor;
                count += (n % factor) + 1;
            } else {
                count += (high + 1) * factor;
            }
            factor *= 10;
        }
        return (int) count;
    }

}
